\ifx\wholebook\relax \else
% ------------------------

\documentclass[b5paper]{ctexart}

\usepackage[cn]{../../prelude}

\setcounter{page}{1}

\begin{document}

%--------------------------

\title{前言}

\author{刘新宇
\thanks{{\bfseries 刘新宇} \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\maketitle
\fi

\markboth{前言}{基本算法}

尽管我们在课堂上学习基本算法，但除了编程竞赛，求职面试，很多人在工作中根本用不上。当人们谈到人工智能和机器学习算法时，实际上说的是数学模型而非基本算法和数据结构。即使在工作中遇到算法，大多数时候程序库中已经实现好了。我们只需要了解如何使用，而不用自己重新实现。

算法在解决一些“有趣”的问题时，会扮演关键角色。作为例子，让我们来看看下面这两个趣题。

\section{最小可用数}
\label{min-free} \index{最小可用数}

理查德$\cdot$伯德提出过一个问题：找出不在一个列表中出现的最小数字（\cite{fp-pearls}第一章）。我们经常使用数字作为标识某一实体的标签，例如身份证号，银行账户，电话号码等等。一个数字或者被占用，或者没有被占用。我们希望找到一个最小的没有被占用数字。假设数字都是非负整数，所有正在被使用的数字记录在一个列表中：

\begin{verbatim}
[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]
\end{verbatim}

不在这个列表中的最小整数是10。这个题目看上去是如此简单，我们可以立即写出下面解法：

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $x \gets 0$
  \Loop
    \If{$x \notin A$}
      \State \Return $x$
    \Else
      \State $x \gets x + 1$
    \EndIf
  \EndLoop
\EndFunction
\end{algorithmic}

其中符号$\notin$的实现如下：

\begin{algorithmic}[1]
\Function{`$\notin$'}{$x, X$}
  \For{$i \gets 1 $ to $|X|$}
    \If{$x = X[i]$}
      \State \Return False
    \EndIf
  \EndFor
  \State \Return True
\EndFunction
\end{algorithmic}

有些编程语言内置了这一线性查找的实现，下面是一段例子代码。

\lstset{language=Python, frame=single}
\begin{lstlisting}
def minfree(lst):
    i = 0
    while True:
        if i not in lst:
            return i
        i = i + 1
\end{lstlisting}

当列表存储了几百万个数字时，这个方法的的性能很快变差。它消耗的时间和列表长度的平方成正比。在一台双核2.10GHz处理器，2G内存的计算机上，其C语言实现需要5.4秒才能在十万个数字中找到答案。当数量上升到一百万时，则耗时达到8分钟。

\subsection{改进}
改进这一解法的关键基于这一事实：对于任何$n$个非负整数$x_1, x_2, ..., x_n$，如果存在小于$n$的可用整数，必然存在某个$x_i$不在$[0, n)$这个范围内。否则这些整数一定是$0, 1, ..., n - 1$的某个排列，这种情况下，最小的可用整数是$n$。于是我们有如下结论：

\be
\textit{minfree}(x_1, x_2, ..., x_n) \leq n
\label{eq:min-free}
\ee

为此我们可以用一个长度为$n + 1$的数组，来标记区间$[0, n]$内的某个整数是否可用。

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $F \gets $[False, False, ..., False] where $|F| = n+1$
  \For{$\forall x \in A$}
    \If{$x < n$}
      \State $F[x] \gets$ True
    \EndIf
  \EndFor
  \For{$i \gets [0, n]$}
    \If{$F[i] =$ False}
      \State \Return $i$
    \EndIf
  \EndFor
\EndFunction
\end{algorithmic}

其中第2行将标志数组中的所有值初始化为假。接着我们遍历$A$中的所有数字，只要小于$n$，就将相应的标记置为真。接下来我们再次扫描标志数组，找到第一个值为假的位置。整个算法用时和$n$成正比。我们使用了$n + 1$而不是$n$个标志，这样无需额外处理，就可以应对$sorted(A) = [0, 1, 2, ..., n-1]$的特殊情况。

虽然这个方法只需要线性时间，但是它需要$O(n)$的空间来存储标志。我们还可以继续优化。每次查找都要申请长度为$n + 1$的数组；查找结束后，这个数组又被释放了。反复的申请和释放会消耗大量时间。我们可以预先准备好足够长的数组，然后每次查找都复用它。另外，我们可以使用二进制的位来保存标志，从而节约空间。下面的C语言例子程序实现了这两点改进：

\begin{lstlisting}[language=C]
#define N 1000000
#define WORD_LENGTH (sizeof(int) * 8)

void setbit(unsigned int* bits, unsigned int i) {
    bits[i / WORD_LENGTH] |= 1 << (i % WORD_LENGTH);
}

int testbit(unsigned int* bits, unsigned int i) {
    return bits[i / WORD_LENGTH] & (1 << (i % WORD_LENGTH));
}

unsigned int bits[N / WORD_LENGTH + 1];

int minfree(int* xs, int n) {
  int i, len = N/WORD_LENGTH + 1;
  for (i = 0; i < len; ++i) {
      bits[i]=0;
  }
  for (i=0; i < n; ++i) {
      if(xs[i] < n) {
          setbit(bits, xs[i]);
      }
  }
  for (i=0; i <= n; ++i) {
      if (!testbit(bits, i)) {
          return i;
      }
  }
}
\end{lstlisting}

在相同的计算机上，这段程序仅用0.023秒就可以处理一百万个数字。

\subsection{分而治之}
我们在速度上的改进是以空间上的消耗为代价的。由于维护了一个长度为$n$的标志数组，当$n$很大时，空间就会成为新的瓶颈。分而治之的策略将问题分解为若干规模较小的子问题，然后逐步解决它们以得到最终的结果。

我们可以将所有满足$x_i \leq \lfloor n/2 \rfloor$的整数放入一个子序列$A'$；将其它整数放入另外一个序列$A''$。根据公式\ref{eq:min-free}，如果序列$A'$的长度正好是$\lfloor n/2 \rfloor$，这说明前一半的整数$A'$已经“满了”，最小可用整数一定可以在$A''$中找到。否则，最小可用整数一定在$A'$中。总之，通过这一划分，问题的规模减小了。

需要注意的是，当在子序列$A''$中递归查找时，边界情况发生了一些变化。我们不再是从0开始寻找最小可用整数，查找的下界变成了$\lfloor n/2 \rfloor + 1$。因此我们的算法应定义为$search(A, l, u)$，其中$l$是下界，$u$是上界。递归的边界条件是当序列为空时，我们返回下界$l$作为结果。

\[
minfree(A) = search(A, 0, |A|-1)
\]

\[
\begin{array}{rcl}
search(\nil, l, u) & = & l \\
search(A, l, u) & = & \begin{cases}
       |A'| = m - l + 1 : & search(A'', m+1, u) \\
       otherwise : & search(A',  l, m) \\
\end{cases}
\end{array}
\]

其中

\[ \begin{array}{rcl}
m & = & \displaystyle \lfloor \frac{l+u}{2} \rfloor \\
A' & = & [ x | x \in A, x \leq m ] \\
A''& = & [ x | x \in A, x > m ] \\
\end{array} \]

这一方法并不需要额外的空间\footnote{递归需要$O(\lg n)$的栈空间，但可以通过尾递归优化消除。}。每次调用需要进行$O(|A|)$次比较来划分出子序列$A'$和$A''$。每次问题的规模都会减半，所以算法用时为$T(n) = T(n/2) + O(n)$，通过主定理化简得到结果$O(n)$。我们也可以这样分析：第一次需要$O(n)$次比较来划分子序列$A'$和$A''$，第二次需要比较$O(n/2)$次，第三次需要比较$O(n/4)$次……总时间为$O(n + n/2 + n/4 + ...) = O(2n) = O(n)$。在定义中我们用表达式$[a | a \in A, p(a)]$来定义列表。它和集合表达式$\{a | a \in A, p(a) \}$有所不同。下面的Haskell例子代码实现了分而治之的算法。

\begin{Haskell}
minFree xs = bsearch xs 0 (length xs - 1)

bsearch xs l u | xs == [] = l
               | length as == m - l + 1 = bsearch bs (m+1) u
               | otherwise = bsearch as l m
    where
      m = (l + u) `div` 2
      (as, bs) = partition (<=m) xs
\end{Haskell}

\subsection{简洁与性能}
有人会担心这一算法的性能。递归的深度为$O(\lg n)$，调用栈的大小也是$O(\lg n)$。我们可以通过将递归转换为迭代来避免空间上的占用：

\begin{algorithmic}[1]
\Function{Min-Free}{$A$}
  \State $l \gets 0, u \gets |A|$
  \While{$u - l > 0$}
    \State $m \gets l + \dfrac{u - l}{2}$
    \State $left \gets l$
    \For{$right \gets l$ to $u - 1$}
      \If{$A[right] \leq m$}
        \State $A[left] \leftrightarrow A[right]$
        \State $left \gets left + 1$
      \EndIf
    \EndFor
    \If{$left < m + 1$}
      \State $u \gets left$
    \Else
      \State $l \gets left$
    \EndIf
  \EndWhile
\EndFunction
\end{algorithmic}

如图\ref{fig:divide}所示，这段程序对数组中的元素进行划分。$left$之前的元素都不大于$m$，而$left$和$right$之间的元素都大于$m$。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.7]{img/divide-by-m.ps}
  \caption{数组划分。位于$0 \leq i < left$的元素满足$A[i] \leq m$，位于$left \leq i < right$的元素满足$A[i] > m$，剩余的元素尚未处理。}
  \label{fig:divide}
\end{figure}

这一解法运行快速并且不需要额外的栈空间。但前面的递归算法更显简洁。不同读者的偏好可能会有所不同。

\section{正规数}

第二道趣题是寻找第1500个正规数。正规数就是只含有2、3、5这三个因子的自然数。因为最大的素因子是5，所以在数论中又叫作5-光滑数。在计算机科学中又叫作哈明数以纪念理查德$\cdot$哈明。2、3、5本身自然也是正规数。$60 = 2^23^15^1$是第25个正规数。数字$21 = 2^03^17^1$由于含有因子7，所以不是正规数。我们定义$1=2^03^05^0$是第0个正规数。前10个正规数如下：

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

\subsection{穷举法}
我们可以从1开始，逐一检查所有自然数，对于每个整数，把2、3、5这些因子不断去掉，然后检查最终结果是否为1：

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \While{$n > 0$}
    \State $x \gets x + 1$
    \If{\Call{Valid?}{$x$}}
      \State $n \gets n - 1$
    \EndIf
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Valid?}{$x$}
  \While{$x \bmod 2 = 0$}
    \State $x \gets \lfloor x / 2 \rfloor$
  \EndWhile
  \While{$x \bmod 3 = 0$}
    \State $x \gets \lfloor x / 3 \rfloor$
  \EndWhile
  \While{$x \bmod 5 = 0$}
    \State $x \gets \lfloor x / 5 \rfloor$
  \EndWhile
  \State \Return $x = 1$ ?
\EndFunction
\end{algorithmic}

穷举法对于较小的$n$没有问题。在同样的计算机上，其C语言实现用时40.39秒才找到第1500个正规数（860934420）。当$n$增加到15000时，即使10分钟也无法结束。

\subsection{构造性解法}
取模和除法是比较耗时\cite{Bentley}，并且这些运算被循环执行了很多次。我们可以转换思路，不再检查一个数是否仅含2、3、5作为因子，而是从这三个因子构造正规数。这样问题就转换为如何从小到大依次产生正规数序列。我们可以使用队列这种数据结构来解决。

队列可以从一侧放入元素，从另一侧取出元素。所以先放入的元素会先被取出。这一特性被称为先进先出FIFO(First-In-First-Out)。我们的思路是先把1作为第0个正规数放入队列。然后不断从队列另一侧取出正规数，分别乘以2、3、5，产生3个新正规数，按照大小顺序将其放入队列。如果新产生的数已存在于队列中，则将其丢弃以避免重复。新产生的正规数还可能小于队列尾部的值，因此在插入时，需要保持它们在队列中的大小顺序。图\ref{fig:queues}描述了这一思路的步骤。

\begin{figure}[htbp]
  \centering
  \subcaptionbox{初始状态，1入队}{\includegraphics[scale=0.5]{img/q1.ps}}
  \hspace{.1\textwidth}
  \subcaptionbox{2、3、5入队}{\includegraphics[scale=0.5]{img/q2.ps}}
  \\
  \subcaptionbox{4、6、10入队}{\includegraphics[scale=0.5]{img/q3.ps}}
  \hspace{.1\textwidth}
  \subcaptionbox{9、15入队，6被丢弃}{\includegraphics[scale=0.5]{img/q4.ps}}
  \caption{使用队列生成正规数的前4步} \label{fig:queues}
\end{figure}

根据这一思路的算法实现如下：

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $Q \gets \nil$
  \State $x \gets 1$
  \State \Call{Enqueue}{$Q, x$}
  \While{$n > 0$}
    \State $x \gets$ \Call{Dequeue}{$Q$}
    \State \Call{Unique-Enqueue}{$Q, 2x$}
    \State \Call{Unique-Enqueue}{$Q, 3x$}
    \State \Call{Unique-Enqueue}{$Q, 5x$}
    \State $n \gets n-1$
  \EndWhile
  \State \Return $x$
\EndFunction
\Statex
\Function{Unique-Enqueue}{$Q, x$}
  \State $i \gets 0, m \gets |Q|$
  \While{$i < m$ and $Q[i] < x$}
    \State $i \gets i + 1$
  \EndWhile
  \If{$i \geq m$ or $x \neq Q[i]$}
    \State \Call{Insert}{$Q, i, x$}
  \EndIf
\EndFunction
\end{algorithmic}

对于长度为$m$的队列，\textproc{insert}函数需要$O(m)$的时间按序、无重复地插入一个新元素。队列的长度会随着$n$线性增加（每取出一个元素后最多插入三个新元素，增加的比率$\leq 2$），总运行时间为$O(1 + 2 + 3 + ... + n) = O(n^2)$。

图\ref{fig:big-O-1q}的数据显示了队列的访问次数和$n$之间的关系，其形状为二次曲线，反映出$O(n^2)$的复杂度。

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.5]{img/big-O-1q.eps}
  \caption{队列访问次数和$n$的关系} \label{fig:big-O-1q}
\end{figure}

在同样的计算机上，对应的C语言实现仅用0.016秒就输出了答案86093442，比穷举法快2500倍。

这一解法也可以用递归的方式给出，令$X$为包含所有正规数的无穷序列$[x_1, x_2, x_3, ...]$。对于每个正规数，将其乘以2得到的仍然是无穷正规数列：$[2x_1, 2x_2, 2x_3, ...]$。同样，依次乘以3和5会得到另外两个无穷正规数列。如果将这3个新无穷数列合并，去除重复元素，然后将1添加到最开始，我们就又得到了$X$。也就是说，下面的等式成立：

\be
  X = 1 : [2x | \forall x \in X]\cup [3x | \forall x \in X] \cup [5x | \forall x \in X]
\ee

其中$x : X$表示将元素$x$连接到列表$X$的前面，从而使$x$成为第一个元素。在Lisp中这个操作称为cons。1是第0个正规数，我们把它放在最前面。为了实现无穷列表的合并，我们递归地定义$\cup$操作。令$X=[x_1, x_2, x_3...]$，$Y=[y_1, y_2, y_3, ...]$为两个无穷序列。$X' = [x_2, x_3, ...]$，$Y'=[y_2, y_3, ...]$表示除去第一个元素后的剩余部分，定义$\cup$为：

\[
X \cup Y = \begin{cases}
  x_1 < y_1: & x_1 : X' \cup Y \\
  x_1 = y_1: & x_1 : X' \cup Y' \\
  y_1 < x_1: & y_1 : X \cup Y' \\
\end{cases}
\]

因为是无穷序列，我们无需处理$X$、$Y$为空的情况。在支持惰性求值的环境中，算法可以实现为如下的例子代码：

\begin{Haskell}
ns = 1 : (map (*2) ns) `merge` (map (*3) ns) `merge` (map (*5) ns)

merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                    | x == y = x : merge xs ys
                    | otherwise = y : merge (x:xs) ys
\end{Haskell}

通过\texttt{ns !! 1500}，可以得到第1500个正规数。在同样的计算机上，这一程序用时0.03秒。

\subsection{队列}
上面的解法虽然快了很多，但会产生重复的元素。它们最终被丢弃了。它需要扫描队列以保证元素有序。入队操作从常数时间退化为线性时间$O(|Q|)$。为了避免重复，我们把所有正规数分成三个类：$Q_2 = \{2^i | i > 0\}$仅包含被2整除的数；$Q_{23} = \{ 2^i3^j | i \geq 0, j > 0 \}$；$Q_{235} = \{ 2^i3^j5^k | i,j \geq 0, k > 0\}$。其中$Q_{23}$要求$j \neq 0$，$Q_{235}$要求$k \neq 0$。这保证了三类数彼此间没有重复。每类数我们都用一个队列来产生。它们初始化为$Q_2=\{ 2 \}$，$Q_{23} = \{ 3\}$和$Q_{235} = \{ 5 \}$。每次从这三个队列的头部选出最小的元素$x$并取出，然后进行下面的检查：

\begin{itemize}
\item 如果$x$是从$Q_2$取出的，我们将$2x$加入$Q_2$，$3x$加入$Q_{23}$，$5x$加入$Q_{235}$。
\item 如果$x$是从$Q_{23}$取出的，我们只将$3x$加入$Q_{23}$，$5x$加入$Q_{235}$。我们不应该将$2x$加入$Q_2$，因为$Q_3$中不允许包含被3整除的数。
\item 如果$x$是从$Q_{235}$取出的，我们只将$5x$加入$Q_{235}$。我们不应该将$2x$加入$Q_2$，$3x$加入$Q_{23}$，因为它们不允许包含被5整除的数。
\end{itemize}

我们不断从这三个队列中取出最小的，直到取出第$n$个元素。图\ref{fig:q235}给出了前4步。

\begin{figure}[htbp]
  \centering
  \subcaptionbox{4、6、10入队}{\includegraphics[scale=0.5]{img/q235-1.ps}}
  \subcaptionbox{9、15入队}{\includegraphics[scale=0.5]{img/q235-2.ps}} \\
  \subcaptionbox{8、12、20入队}{\includegraphics[scale=0.5]{img/q235-3.ps}} \\
  \subcaptionbox{25入队}{\includegraphics[scale=0.5]{img/q235-4.ps}}
  \caption{使用三个队列$Q_2$、$Q_{23}$和$Q_{235}$来构造正规数的前4步。初始时它们包含2、3、5为唯一元素}
  \label{fig:q235}
\end{figure}

按照这个思路，算法可以实现如下。

\begin{algorithmic}[1]
\Function{Regular-Number}{$n$}
  \State $x \gets 1$
  \State $Q_2 \gets \{ 2 \}$, $Q_{23} \gets \{ 3 \}$, $Q_{235} \gets \{ 5 \}$
  \While{$n > 0$}
    \State $x \gets min$(\Call{Head}{$Q_2$}, \Call{Head}{$Q_{23}$}, \Call{Head}{$Q_{235}$})
    \If{$x =$ \Call{Head}{$Q_2$}}
      \State \Call{Dequeue}{$Q_2$}
      \State \Call{Enqueue}{$Q_2, 2x$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \ElsIf{$x=$ \Call{Head}{$Q_{23}$}}
      \State \Call{Dequeue}{$Q_{23}$}
      \State \Call{Enqueue}{$Q_{23}, 3x$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \Else
      \State \Call{Dequeue}{$Q_{235}$}
      \State \Call{Enqueue}{$Q_{235}, 5x$}
    \EndIf
    \State $n \gets n - 1$
  \EndWhile
  \State \Return $x$
\EndFunction
\end{algorithmic}

算法循环$n$次。每次循环，它从三个队列中取出最小的一个元素，这一步需要常数时间。接着它根据取出元素所在的队列，产生一到三个新元素放入队列，这一步也是常数时间。因此整个算法的复杂度是$O(n)$的。

\section{小结}
两个趣题表面上看来都能用简单的穷举法解决。但随着问题规模的增加，我们不得不寻求更好的解法。很多以前难以解决的问题，我们可以通过编程用新的方式找到答案。本书介绍常见的基本算法和数据结构，同时给出函数式和命令式的对比实现。主要参考了冈崎的著作\cite{okasaki-book}和经典的算法教材\cite{CLRS}。本书尽量避免依赖于特定的编程语言。一方面读者会有自己的语言偏好，另一方面编程语言也在不断变化。为此我们主要使用伪代码和数学记法对算法进行定义，而附以一些例子代码片段。函数式的代码例子类似Haskell，命令式的代码例子是一些常见语言的混合。这些示例并不一定严格遵循某些语言规范。

本书中文版《算法新解》于2017年出版。2020年底开始进行重写。电子版可以在github上获得，如果希望获得纸质版，请联系liuxinyu95@gmail.com。

\begin{Exercise}
\Question{最小可用数趣题中，所有数都是非负整数。我们可以利用正负号来标记一个数字是否存在。首先扫描一遍列表，令列表长度为$n$，对于任何绝对值小于$n$的数$|x| < n$，将位置$|x|$上的数字置为负数。之后再次扫描一遍列表，找到第一个整数所在的位置就是答案。编程实现这一算法。}

\Question{$n$个数字1, 2, ..., $n$，经过某一处理后，它们的顺序被打乱了，并且某一个数$x$被改成了$y$。假设$1 \leq y \leq n$，设计一个方法能够在线性时间、常数空间内找出$x$和$y$。}

\Question{下面是一段求正规数的代码。它是一种队列解法么？
\begin{lstlisting}[language = Bourbaki]
Int regularNum(Int m) {
    nums = Int[m + 1]
    n = 0, i = 0, j = 0, k = 0
    nums[0] = 1
    x2 = 2 * nums[i]
    x3 = 3 * nums[j]
    x5 = 5 * nums[k]
    while (n < m) {
        n = n + 1
        nums[n] = min(x2, x3, x5)
        if (x2 == nums[n]) {
            i = i + 1
            x2 = 2 * nums[i]
        }
        if (x3 == nums[n]) {
            j = j + 1
            x3 = 3 * nums[j]
        }
        if (x5 == nums[n]) {
            k = k + 1
            x5 = 5 * nums[k]
        }
    }
    return nums[m];
}
\end{lstlisting}
}
\end{Exercise}

\ifx\wholebook\relax \else
\begin{thebibliography}{99}

\bibitem{fp-pearls}
Richard Bird. ``Pearls of functional algorithm design''. Cambridge University Press; 1 edition (November 1, 2010). ISBN-10: 0521513383. pp1 - pp6.

\bibitem{Bentley}
Jon Bentley. ``Programming Pearls(2nd Edition)''. Addison-Wesley Professional; 2 edition (October 7, 1999). ISBN-13: 978-0201657883 （中文版：《编程珠玑》）

\bibitem{okasaki-book}
Chris Okasaki. ``Purely Functional Data Structures''. Cambridge university press, (July 1, 1999), ISBN-13: 978-0521663502

\bibitem{CLRS}
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition''. The MIT Press, 2001. ISBN: 0262032937. （中文版：《算法导论》）

\end{thebibliography}

\expandafter\enddocument
%\end{document}

\fi
